/*
 * @lc app=leetcode.cn id=5 lang=java
 *
 * [5] 最长回文子串
 */

// @lc code=start
class Solution {
    public String longestPalindrome(String s) {
        int len=s.length();
        if(len<2){//只有1个字符直接返回即可
            return s;
        }
        //采用动态规划实现，定义dp[i][j]为字符串i到j的子串是否回文串
        boolean[][] dp=new boolean[len][len];
        //初始化：长度为1的子串均为回文串
        for(int i=0;i<len;i++){
            dp[i][i]=true;
        }
        char[] schar=s.toCharArray();
        int begin=0;
        int maxlen=1;//初始化为1，是因为最小子串为1
        //从长度为2的子串开始递推,注意长度为2的子串判断
        for(int L=2;L<=len;L++){
            // 枚举所有长度为L的子串
            for(int i=0;i<len;i++){
                //右边界j-i+1=L,得到j=L+i-1
                int j=L+i-1;
                if(j>=len){//右边界越界，即退出
                    break;
                }
                if(schar[i]!=schar[j]){//子串左右字符不等，即dp[i][j]的子串不是回文串
                    dp[i][j]=false;
                }else{
                    if(j-i<3){//子串为3时，两端相等，一定为ture
                        dp[i][j]=true;
                    }else{
                        dp[i][j]=dp[i+1][j-1];
                    } 
                }

                if(dp[i][j]==true&&L>maxlen){
                    maxlen=L;
                    begin=i;
                }
            }
        }
        return s.substring(begin, begin+maxlen);


    }
}
// @lc code=end

